home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / fscompr / deflate.c < prev    next >
C/C++ Source or Header  |  1997-10-11  |  45KB  |  1,210 lines
  1. /* deflate.c -- compress data using the deflation algorithm
  2.  * Copyright (C) 1995-1996 Jean-loup Gailly.
  3.  * For conditions of distribution and use, see copyright notice in zlib.h 
  4.  */
  5.  
  6. /*
  7.  *  ALGORITHM
  8.  *
  9.  *      The "deflation" process depends on being able to identify portions
  10.  *      of the input text which are identical to earlier input (within a
  11.  *      sliding window trailing behind the input currently being processed).
  12.  *
  13.  *      The most straightforward technique turns out to be the fastest for
  14.  *      most input files: try all possible matches and select the longest.
  15.  *      The key feature of this algorithm is that insertions into the string
  16.  *      dictionary are very simple and thus fast, and deletions are avoided
  17.  *      completely. Insertions are performed at each input character, whereas
  18.  *      string matches are performed only when the previous match ends. So it
  19.  *      is preferable to spend more time in matches to allow very fast string
  20.  *      insertions and avoid deletions. The matching algorithm for small
  21.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  22.  *      is used to find longer strings when a small match has been found.
  23.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  24.  *      (by Leonid Broukhis).
  25.  *         A previous version of this file used a more sophisticated algorithm
  26.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  27.  *      time, but has a larger average cost, uses more memory and is patented.
  28.  *      However the F&G algorithm may be faster for some highly redundant
  29.  *      files if the parameter max_chain_length (described below) is too large.
  30.  *
  31.  *  ACKNOWLEDGEMENTS
  32.  *
  33.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  34.  *      I found it in 'freeze' written by Leonid Broukhis.
  35.  *      Thanks to many people for bug reports and testing.
  36.  *
  37.  *  REFERENCES
  38.  *
  39.  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
  40.  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
  41.  *
  42.  *      A description of the Rabin and Karp algorithm is given in the book
  43.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  44.  *
  45.  *      Fiala,E.R., and Greene,D.H.
  46.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  47.  *
  48.  */
  49.  
  50. /* $Id: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
  51.  
  52. #include "deflate.h"
  53.  
  54. char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly ";
  55. /*
  56.   If you use the zlib library in a product, an acknowledgment is welcome
  57.   in the documentation of your product. If for some reason you cannot
  58.   include such an acknowledgment, I would appreciate that you keep this
  59.   copyright string in the executable of your product.
  60.  */
  61.  
  62. /* ===========================================================================
  63.  *  Function prototypes.
  64.  */
  65. typedef enum {
  66.     need_more,      /* block not completed, need more input or more output */
  67.     block_done,     /* block flush performed */
  68.     finish_started, /* finish started, need only more output at next deflate */
  69.     finish_done     /* finish done, accept no more input or output */
  70. } block_state;
  71.  
  72. typedef block_state (*compress_func) OF((deflate_state *s, int flush));
  73. /* Compression function. Returns the block state after the call. */
  74.  
  75. local void fill_window    OF((deflate_state *s));
  76. local block_state deflate_stored OF((deflate_state *s, int flush));
  77. local block_state deflate_fast   OF((deflate_state *s, int flush));
  78. local block_state deflate_slow   OF((deflate_state *s, int flush));
  79. local void lm_init        OF((deflate_state *s));
  80. local void putShortMSB    OF((deflate_state *s, uInt b));
  81. local void flush_pending  OF((z_streamp strm));
  82. local int read_buf        OF((z_streamp strm, charf *buf, unsigned size));
  83. #ifdef ASMV
  84.       void match_init OF((void)); /* asm code initialization */
  85.       uInt longest_match  OF((deflate_state *s, IPos cur_match));
  86. #else
  87.       local uInt longest_match  OF((deflate_state *s, IPos cur_match));
  88. #endif
  89.  
  90. #ifdef DEBUG
  91. local  void check_match OF((deflate_state *s, IPos start, IPos match,
  92.                             int length));
  93. #endif
  94.  
  95. /* ===========================================================================
  96.  * Local data
  97.  */
  98.  
  99. #define NIL 0
  100. /* Tail of hash chains */
  101.  
  102. #ifndef TOO_FAR
  103. #  define TOO_FAR 4096
  104. #endif
  105. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  106.  
  107. #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  108. /* Minimum amount of lookahead, except at the end of the input file.
  109.  * See deflate.c for comments about the MIN_MATCH+1.
  110.  */
  111.  
  112. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  113.  * the desired pack level (0..9). The values given below have been tuned to
  114.  * exclude worst case performance for pathological files. Better values may be
  115.  * found for specific files.
  116.  */
  117. typedef struct config_s {
  118.    ush good_length; /* reduce lazy search above this match length */
  119.    ush max_lazy;    /* do not perform lazy search above this match length */
  120.    ush nice_length; /* quit search above this match length */
  121.    ush max_chain;
  122.    compress_func func;
  123. } config;
  124.  
  125. local config configuration_table[10] = {
  126. /*      good lazy nice chain */
  127. /* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
  128. /* 1 */ {4,    4,  8,    4, deflate_fast}, /* maximum speed, no lazy matches */
  129. /* 2 */ {4,    5, 16,    8, deflate_fast},
  130. /* 3 */ {4,    6, 32,   32, deflate_fast},
  131.  
  132. /* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches */
  133. /* 5 */ {8,   16, 32,   32, deflate_slow},
  134. /* 6 */ {8,   16, 128, 128, deflate_slow},
  135. /* 7 */ {8,   32, 128, 256, deflate_slow},
  136. /* 8 */ {32, 128, 258, 1024, deflate_slow},
  137. /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */
  138.  
  139. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  140.  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  141.  * meaning.
  142.  */
  143.  
  144. #define EQUAL 0
  145. /* result of memcmp for equal strings */
  146.  
  147. struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
  148.  
  149. /* ===========================================================================
  150.  * Update a hash value with the given input byte
  151.  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  152.  *    input characters, so that a running hash key can be computed from the
  153.  *    previous key instead of complete recalculation each time.
  154.  */
  155. #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
  156.  
  157.  
  158. /* ===========================================================================
  159.  * Insert string str in the dictionary and set match_head to the previous head
  160.  * of the hash chain (the most recent string with same hash key). Return
  161.  * the previous length of the hash chain.
  162.  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  163.  *    input characters and the first MIN_MATCH bytes of str are valid
  164.  *    (except for the last MIN_MATCH-1 bytes of the input file).
  165.  */
  166. #define INSERT_STRING(s, str, match_head) \
  167.    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  168.     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
  169.     s->head[s->ins_h] = (Pos)(str))
  170.  
  171. /* ===========================================================================
  172.  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  173.  * prev[] will be initialized on the fly.
  174.  */
  175. #define CLEAR_HASH(s) \
  176.     s->head[s->hash_size-1] = NIL; \
  177.     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
  178.  
  179. /* ========================================================================= */
  180. int EXPORT deflateInit_(strm, level, version, stream_size)
  181.     z_streamp strm;
  182.     int level;
  183.     const char *version;
  184.     int stream_size;
  185. {
  186.     return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
  187.              Z_DEFAULT_STRATEGY, version, stream_size);
  188.     /* To do: ignore strm->next_in if we use it as window */
  189. }
  190.  
  191. /* ==============================================================